home *** CD-ROM | disk | FTP | other *** search
/ CD ROM Paradise Collection 4 / CD ROM Paradise Collection 4 1995 Nov.iso / arcers / tar316.zip / LZPACK.C < prev    next >
Text File  |  1994-06-29  |  8KB  |  295 lines
  1. /* lzpack.c - compress encode/decode file for Tar program (see file tar.c)
  2.  * Programmer: T.V.Shaporev
  3.  * Prepared for release 19 Oct 1990
  4.  * Called by store() (see file store.c) and extract() (see file extract.c)
  5.  */
  6. /* Source:
  7.  *    LZARI.C -- A Data Compression Program
  8.  *    4/7/1989 Haruhiko Okumura
  9.  *    PC-VAN        SCIENCE
  10.  *    NIFTY-Serve    PAF01022
  11.  *    CompuServe    74050,1022
  12.  */
  13.  
  14. /* Modified 30.9.90 Tim Shaporev */
  15.  
  16. #include "sysup.h"
  17.  
  18. extern char v_flag;
  19.  
  20. #include <stdio.h>
  21.  
  22. #ifdef UNIX
  23.     char *malloc();
  24.     void free();
  25. #endif
  26.  
  27. #ifdef MSDOS
  28. #    include <stdlib.h>
  29. #endif
  30.  
  31. #define    pare(x)  ((x)+(x))
  32. #define half(x)  ((x)>>1)
  33.  
  34. #include "sysup.h"
  35.  
  36. #ifdef MSDOS
  37. #    define __ARGS__(x) x
  38. #endif
  39. #ifndef __ARGS__
  40. #    define __ARGS__(x) ()
  41. #endif
  42.  
  43. #include "lzpack.h"
  44.  
  45. static  int    GetBit        __ARGS__(( void ));
  46. static  void    StartModel    __ARGS__(( void ));
  47. static  void    UpdateModel    __ARGS__(( int ));
  48. static  int    BinarySearchSym    __ARGS__(( unsigned ));
  49. static  int    BinarySearchPos    __ARGS__(( unsigned ));
  50. static  void    StartDecode    __ARGS__(( void ));
  51. static  int    DecodeChar    __ARGS__(( void ));
  52. static  int    DecodePosition    __ARGS__(( void ));
  53.  
  54. /********** Bit I/O **********/
  55. static int  (*getbyte) __ARGS__(( void ));
  56. static void (*putbyte) __ARGS__(( int ));
  57. static short GetBuf, GetMask;
  58.  
  59. #define InitGetBit (GetMask=0)
  60.  
  61. static int GetBit() /* Get one bit (0 or 1) */
  62. {
  63.    if ((GetMask >>= 1) == 0) {
  64.       GetBuf = (*getbyte)();
  65.       GetMask = 128;
  66.    }
  67.    return (GetBuf & GetMask) != 0;
  68. }
  69.  
  70. /********** LZSS with multiple binary trees **********/
  71. #define N      4096 /* size of ring buffer */
  72. #define F        60 /* upper limit for match_length */
  73. #define THRESHOLD 2 /* encode string into position and length */
  74.                     /* if match_length is greater than this */
  75. #define NIL       N /* index for root of binary search trees */
  76. #define INC(x) ((x)=((x)+1)&(N-1))
  77.  
  78. /* ring buffer of size N, with extra F-1 bytes for string comparison */
  79. /* unsigned char text_buf[N+F-1]; */
  80. static short *core = (short *)0;
  81.  
  82. #define position_cum ((unsigned short *)core)
  83. #if 0
  84. #define lson         (core + N+1)
  85. #define rson         (core + N+1 + N+1)
  86. #define dad         (core + N+1 + N+1 + N+257)
  87. #define text_buf ((unsigned char *)(core + N+1 + N+1 + N+257 + N+1))
  88. #else
  89. #define text_buf ((unsigned char *)core)
  90. #endif
  91.  
  92. int lzgetmem()
  93. {
  94.    if (!core) {
  95.       core=(short*)malloc(/*(N+1 + N+1 + N+257 + N+1)*sizeof(short)+*/ N+F);
  96.       if (!core) return -1;
  97.    }
  98.    return 0;
  99. }
  100.  
  101. void lzrelmem()
  102. {
  103.    if (core) free((char *)core); core = (short *)0;
  104. }
  105.  
  106. /********** Arithmetic Compression **********/
  107.  
  108. /*  If you are not familiar with arithmetic compression, you should read
  109.         I. E. Witten, R. M. Neal, and J. G. Cleary,
  110.             Communications of the ACM, Vol. 30, pp. 520-540 (1987),
  111.     from which much have been borrowed.  */
  112.  
  113. #define M   15
  114.  
  115. /*    Q1 (= 2 to the M) must be sufficiently large, but not so
  116.     large as the unsigned long 4 * Q1 * (Q1 - 1) overflows.  */
  117.  
  118. #define Q1  (1L << M)
  119. #define Q2  (2 * Q1)
  120. #define Q3  (3 * Q1)
  121. #define Q4  (4 * Q1)
  122. #define MAX_CUM (Q1 - 1)
  123.  
  124. #define N_CHAR  (256 - THRESHOLD + F)
  125.     /* character code = 0, 1, ..., N_CHAR - 1 */
  126.  
  127. static unsigned long /*int*/ low = 0, high = Q4, value = 0;
  128. static short shifts = 0; /* counts for magnifying low and high around Q2 */
  129. static short char_to_sym[N_CHAR], sym_to_char[N_CHAR + 1];
  130. static unsigned short sym_freq[N_CHAR + 1]; /* frequency for symbols */
  131. static unsigned short sym_cum[N_CHAR + 1]; /* cumulative freq for symbols */
  132. #if 0
  133. unsigned short position_cum[N + 1];   /* cumulative freq for positions */
  134. #endif
  135.  
  136. static void StartModel()  /* Initialize model */
  137. {
  138.    register i; register ch, sym;
  139.  
  140.    sym_cum[N_CHAR] = 0;
  141.    for (sym = N_CHAR; sym >= 1; sym--) {
  142.       ch = sym - 1;
  143.       char_to_sym[ch] = sym;  sym_to_char[sym] = ch;
  144.       sym_freq[sym] = 1;
  145.       sym_cum[sym - 1] = sym_cum[sym] + sym_freq[sym];
  146.    }
  147.    sym_freq[0] = 0;  /* sentinel (!= sym_freq[1]) */
  148.    position_cum[N] = 0;
  149.    for (i = N; i >= 1; i--)
  150.       position_cum[i - 1] = position_cum[i] + 10000 / (i + 200);
  151.    /* empirical distribution function (quite tentative) */
  152.    /* Please devise a better mechanism! */
  153. }
  154.  
  155. static void UpdateModel(sym)
  156. register int sym;
  157. {
  158.    register i; register c; register ch_i, ch_sym;
  159.  
  160.     if (sym_cum[0] >= MAX_CUM) {
  161.         c = 0;
  162.         for (i = N_CHAR; i > 0; i--) {
  163.             sym_cum[i] = c;
  164.             c += (sym_freq[i] = (sym_freq[i] + 1) >> 1);
  165.         }
  166.         sym_cum[0] = c;
  167.     }
  168.     for (i = sym; sym_freq[i] == sym_freq[i - 1]; i--) ;
  169.     if (i < sym) {
  170.         ch_i = sym_to_char[i];    ch_sym = sym_to_char[sym];
  171.         sym_to_char[i] = ch_sym;  sym_to_char[sym] = ch_i;
  172.         char_to_sym[ch_i] = sym;  char_to_sym[ch_sym] = i;
  173.     }
  174.     sym_freq[i]++;
  175.     while (--i >= 0) sym_cum[i]++;
  176. }
  177.  
  178. static int BinarySearchSym(x)
  179. register unsigned int x;
  180. /* 1      if x >= sym_cum[1],
  181.    N_CHAR if sym_cum[N_CHAR] > x,
  182.    i such that sym_cum[i - 1] > x >= sym_cum[i] otherwise */
  183. {
  184.     register i; register j; register k;
  185.  
  186.     i = 1;  j = N_CHAR;
  187.     while (i<j) if (sym_cum[k=half(i+j)] > x) i=k+1; else j=k;
  188.     return i;
  189. }
  190.  
  191. static int BinarySearchPos(x)
  192. register unsigned int x;
  193. /* 0 if x >= position_cum[1],
  194.    N - 1 if position_cum[N] > x,
  195.    i such that position_cum[i] > x >= position_cum[i + 1] otherwise */
  196. {
  197.     register i; register j; register k;
  198.  
  199.     i = 1;  j = N;
  200.     while (i<j) if (position_cum[k = half(i+j)] > x) i=k+1; else j=k;
  201.     return i-1;
  202. }
  203.  
  204. static void StartDecode()
  205. {
  206.     register i;
  207.  
  208.     for (i=0; i<M+2; i++) {
  209.        value = pare(value) + GetBit();
  210.     }
  211. }
  212.  
  213. static int DecodeChar()
  214. {
  215.     register unsigned long range;
  216.     register sym, ch;
  217.  
  218.     range = high - low;
  219.     sym = BinarySearchSym((unsigned int)
  220.         (((value - low + 1) * sym_cum[0] - 1) / range));
  221.     high = low + (range * sym_cum[sym - 1]) / sym_cum[0];
  222.     low +=       (range * sym_cum[sym    ]) / sym_cum[0];
  223.     for (;;) {
  224.         if (low >= Q2) {
  225.             value -= Q2;  low -= Q2;  high -= Q2;
  226.         } else if (low >= Q1 && high <= Q3) {
  227.             value -= Q1;  low -= Q1;  high -= Q1;
  228.         } else if (high > Q2) break;
  229.         low += low;  high += high;
  230.         value = pare(value) + GetBit();
  231.     }
  232.     ch = sym_to_char[sym];
  233.     UpdateModel(sym);
  234.     return ch;
  235. }
  236.  
  237. static int DecodePosition()
  238. {
  239.     register unsigned long range;
  240.     register position;
  241.  
  242.     range = high - low;
  243.     position = BinarySearchPos((unsigned int)
  244.         (((value - low + 1) * position_cum[0] - 1) / range));
  245.     high = low + (range * position_cum[position    ]) / position_cum[0];
  246.     low +=       (range * position_cum[position + 1]) / position_cum[0];
  247.     for (;;) {
  248.         if (low >= Q2) {
  249.             value -= Q2;  low -= Q2;  high -= Q2;
  250.         } else if (low >= Q1 && high <= Q3) {
  251.             value -= Q1;  low -= Q1;  high -= Q1;
  252.         } else if (high > Q2) break;
  253.         low += low;  high += high;
  254.         value = pare(value) + GetBit();
  255.     }
  256.     return position;
  257. }
  258.  
  259. long lzdecode(fget, fput, textsize)
  260. /* Attemt to read after end of file IS NOT ERROR !!! Horror */
  261. int  (*fget) __ARGS__ ((void));
  262. void (*fput) __ARGS__ ((int));
  263. long textsize;
  264. {
  265.    register i; register r; register c;
  266.    register unsigned long count;
  267.  
  268.    getbyte = fget; putbyte = fput;
  269.  
  270.    low = 0; high = Q4; value = 0; shifts = 0;
  271.    InitGetBit;
  272.  
  273.    count = 0;
  274.    StartDecode();
  275.    StartModel();
  276.    for (i=0; i<N-F; i++) text_buf[i] = ' ';
  277.    r = N-F;
  278.    while (count < textsize) {
  279.       if ((c = DecodeChar()) < 256) {
  280.          (*putbyte)(text_buf[r] = c);
  281.          INC(r);
  282.          count++;
  283.       } else {
  284.          i = (r - DecodePosition() - 1) & (N-1);
  285.          c -= 255 - THRESHOLD;
  286.          for (; c; c--) {
  287.             (*putbyte)(text_buf[r] = text_buf[i]);
  288.             INC(i); INC(r);
  289.             count++;
  290.          }
  291.       }
  292.    }
  293.    return count;
  294. }
  295.